package pers.vic.basics.leetcode;

import java.util.*;

/**
 * @description: 40. 组合总和 II  回溯 {@literal https://leetcode-cn.com/problems/combination-sum-ii/}
 * @author Vic.xu
 * @date: 2020/12/3 0003 9:18
 */
public class J0040_M_CombinationSum2 {
    /*
    给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
    candidates 中的每个数字在每个组合中只能使用一次。
    说明：
    所有数字（包括目标数）都是正整数。
    解集不能包含重复的组合。 
     */

    /**
     * 还是回溯 看来leetcode是铁了心要教会我怎么写回溯啊
     */
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        Set<List<Integer>> result = new HashSet<>();
        Deque<Integer> combination = new ArrayDeque<>();
        dfs(candidates, result, combination, target, 0);
        return new ArrayList<>(result);
    }

    private static void dfs(int[] candidates, Set<List<Integer>> result, Deque<Integer> combination, int target, int begin) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            result.add(new ArrayList<>(combination));
        }
        for (int i = begin; i < candidates.length; i++) {
            int cur = candidates[i];
            if (cur > target) {
                return;
            }
            combination.add(cur);
            dfs(candidates, result, combination, target - cur, i+1);
            combination.removeLast();
        }
    }

    public static void main(String[] args) {
        int[] candidates = {10,1,2,7,6,1,5};
        int target = 8;
        combinationSum2(candidates, target).forEach(System.out::println);
        System.out.println(Integer.toBinaryString(224));
        //0
        System.out.println(19&224);
        //0
        System.out.println(0b11100000&0b00010011);
        System.out.println(Integer.toBinaryString(243));
        int a =0b101110010000%0b10011;
        System.out.println(Integer.toBinaryString(a));
    }
}
